package com.leetcode.No0497;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @program: Solution
 * @description: 非重叠矩形中的随机点
 * 被相同概率选中的整数点是属于所有矩阵的，为此先给所有矩阵的整数点做一个排序，
 * 再选出一个随机的数字指定一个整数点
 * 矩阵排序规则：按照rects数组的顺序来
 * 矩阵内整数点排序规则：从矩阵左下角向右上角数，先横着数，再竖着数
 * @author: Wang Zhihua
 * @date: 2022-06-09
 */
public class Solution2 {

    private int[][] rects;
    private int[] nodeNum;
    private int nodeSum;

    public Solution2(int[][] rects) {
        this.rects = rects;

        nodeNum = new int[rects.length];
        nodeSum = 0;
        for (int i = 0; i < rects.length; ++i) {
            int x1 = rects[i][0]; // 矩形左下角x
            int y1 = rects[i][1]; // 矩形左下角y
            int x2 = rects[i][2]; // 矩形右上角x
            int y2 = rects[i][3]; // 矩形右上角y
            int num = (x2 - x1 + 1) * (y2 - y1 + 1);
            nodeNum[i] = (i > 0 ? nodeNum[i - 1] : 0) + num;
            nodeSum += num;
        }
    }

    public int[] pick() {
        Random random = new Random();
        int k = random.nextInt(nodeSum); // 所有矩阵的第K个整数点，从0开始

        int ind = binarySearch(nodeNum, 0, nodeNum.length - 1, k + 1); // 二分法找到第K个整数点所在矩阵的索引
        int internalK = k - (ind > 0 ? nodeNum[ind - 1] : 0); // 矩阵内部的第K个整数点，从0开始数
        int xLen = rects[ind][2] - rects[ind][0] + 1; // 矩阵 行的长度

        int[] result = new int[2];
        result[0] = rects[ind][0] + (internalK % xLen);
        result[1] = rects[ind][1] + (internalK / xLen);

        return result;
    }

    /**
     * 二分查找，在数组的左右边界之间找到一个元素，这个元素是第一个>=目标数字的
     * @param array 要查找的数组，已从小到大排序过
     * @param left 左边界，包含
     * @param right 右边界，包含
     * @param target 目标数字
     * @return
     */
    private int binarySearch(int[] array, int left, int right, int target) {
        if (left == right) {
            return right;
        }
        int middle = (left + right) >> 1;
        if (array[middle] < target) {
            return binarySearch(array, middle + 1, right, target);
        } else {
            return binarySearch(array, left, middle, target);
        }
    }

    public static void main(String[] args) {
//        int[][] nums = {{-2,-2,1,1},{2,2,4,6}};
        int[][] nums = {{82918473,-57180867,82918476,-57180863},{83793579,18088559,83793580,18088560},
                {66574245,26243152,66574246,26243153},{72983930,11921716,72983934,11921720}};
        Solution2 solution = new Solution2(nums);
        for (int i = 0; i< 100; ++i) {
            int[] pick = solution.pick();
            System.out.println(Arrays.toString(pick));

            boolean right = false;
            for (int[] numCoor : nums) {
                if (numCoor[0] <= pick[0] && pick[0] <= numCoor[2] && numCoor[1] <= pick[1] && pick[1] <= numCoor[3]) {
                    right = true;
                    break;
                }
            }
            if (!right) {
                System.out.println("此整数点不符合条件: " + Arrays.toString(pick));
            }
        }
    }

}
